package zuo.test1;

import sun.util.locale.provider.FallbackLocaleProviderAdapter;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @Author: Forx
 * @Data: 2021/6/12
 * @Desc: Algorithm - zuo.test1
 * @Version: v1.0
 */
/*
* 一:    在一个数组中有一个数出现奇数次
*     其余的数都是偶数次,怎么找出现
*     奇数次的这个数
*       findOdd 解决
*
*       如果有两个数出现奇数次怎么找到
*       findOdd2-findOdd2Plus   解决
*
* 二:    插入排序  insertSort
* 三:    二分查找  binarySearch
* 四:    局部最小值,找到一个无序数组中同时
*       小于左右两边的局部最小值,且这
*       个数组中的两个相邻元素不相等
*       要求效率好于O(N)
*       findPartMin 解决
*
*
* */
public class test0 {
    public static void   testSort(){
        int testTime = 50000;
        int maxVlaue = 100;
        int maxLen = 500;
        boolean flag = false;
        for (int i = 0; i < testTime; i++) {
            flag = true;
            int[] in = generateRandomBuff(maxVlaue,maxLen);
            int[] in2 = copy(in);
            System.out.println(i+"st\t"+"Waitting Sort:"+in);
            Arrays.sort(in2);
            insertSort(in);
            for (int j = 0; j < in.length; j++) {
                if(in[j] != in2[j]){
                    System.out.println("Sort err");
                    System.out.println("\t\t" + "My sort:" + in);
                    System.out.println("\t\t" + "Right sort:" + in2);
                    flag = false;
                    break;
                }
            }
            if(flag){
                System.out.println("\t\t[OK!]");
            }else {
                System.out.println("\t\t[FAILED!]");
            }

        }

    }
    public static int[] generateRandomBuff(int maxValue,int maxLen){
        int[] buff = new int[(int)(Math.random()*maxLen) + 1];
        for (int i = 0; i < buff.length; i++) {
            buff[i] =(int) (Math.random()*maxValue) +1;
        }
        return buff;
    }
    public static int[] copy(int[] in){
        int[] out = new int[in.length];
        for (int i = 0; i < in.length; i++) {
            out[i] = in[i];
        }
        return out;
    }





    public static void main(String[] args) {
//        int[] buff = {1,1,2,2,3,3,3,4,4};
//        System.out.println(findOdd(buff));


//        int[] buff2 = {1,1,2,2,4,4,4,3,3,3};
//        findOdd2(buff2);

//        int[] buff3 = {1,1,2,2,4,4,4,3,3,3};
//        insertSort(buff2);

//        int[] buff4 = {1,2,3,4,5,7,7,8};
//        System.out.println(binarySearch(buff4,4));
//        System.out.println(binarySearch(buff4,6));

//        int[] buff5 = {23,3,4,5,8,10,4,34};
//        System.out.println(findPartMin(buff5));
//        int[] buff6 = {123,33,14,5,4,3,2,1};
//        System.out.println(findPartMin(buff6));
        testSort();

    }

    public static int findOdd(int[] in){
        int ans = 0;
        for (int i = 0; i < in.length; i++) {
            ans^=in[i];
        }
        return ans;
    }

    /**
     * 已知数组中只有两个数出现奇数次,假设这两个数是a和b
     * 则ans = a^b   且   ans!=0
     * 我们找到ans中不为1的那一个比特位,a和b中在这一位上
     * 必不相同,所以我们可以借此将数组中的数分成两组,使用
     * temp来异或这一位为1的元素,最后temp必为a或者b
     * 最后再用ans^=temp;将两数分离
     * */

    public static int findOdd2(int[] in){
        int ans = 0;
        int temp = 0;
        for (int i = 0; i < in.length; i++) {
            ans^=in[i];
        }
        /** ********************/
        int setBitIndex = 0;
        while ((1&(ans>>setBitIndex)) != 1){    /*计算出右边第一个不为1的bit位的索引*/
            setBitIndex++;
        }
        /*
        * 还有一种写法
        * int cal = ans & (~ans + 1)
        * 这是常规说法,要记住
        * */
        /** ********************/
        int cal = 1<<setBitIndex;
        for (int elm : in) {
            if((cal & elm) !=0 ){
                temp^=elm;
            }
        }
        ans^=temp;
        System.out.println(ans+"\t"+temp);
        return ans;
    }
    public static void findOdd2Plus(int[] in){
        int ans = 0;
        int temp = 0;
        for (int i = 0; i < in.length; i++) {
            ans^=in[i];
        }
        int cal = ans & (~ans + 1);
        for (int elm : in) {
            if((cal & elm) !=0 ){
                temp^=elm;
            }
        }
        System.out.println(ans+"\t"+temp);
    }

    public static void swap(int[] in,int index1,int index2){
        in[index1]^=in[index2];
        in[index2]^=in[index1];
        in[index1]^=in[index2];
    }

    /*O(N^2)*/
    public static void insertSort(int[] in){
            if(in.length==0 || in.length == 1) return;
        for (int i = 1; i < in.length; i++) {
//            for (int j = i; j > 0 ; j--) {
//                if(in[j] < in[j-1]){
//                    swap(in,j,j-1);
//                }else {
//                    break;
//                }
//
//            }
            /**
             * 第二个for循环可以简写成这样
             * */
            for (int j = i; j > 0 && in[j] < in[j-1]; j--) {
                 swap(in,j,j-1);
            }
        }
    }

    public static int binarySearch(int[] in,int elem){
        int left = 0,right = in.length-1;

        while (left!=right){
            int mid = (left+right)/2;
            if(in[mid] > elem)
                right = mid-1;
            if(in[mid] < elem)
                left = mid+1;
            if(in[mid] == elem)
                return mid;
        }
        return -1;
    }
    public static int findPartMin(int[] in){
        if(in.length <=1)return -1;
        if(in[1] > in[0]) return 0;
        if(in[in.length-1] < in[in.length-2])return in.length-1;
        int left = 1,right = in.length-2;
        while (left<right){
            int mid = (left+right)/2;//这种计算中点可能会溢出所以不好,应该写成l+(r+l)>>1
            if(in[mid] > in[mid-1]){
                right = mid-1;
                continue;
            }
            if(in[mid] > in[mid+1]){
                left = mid+1;
                continue;
            }
            return mid;
        }
        return -1;
    }
    public static int calculateSetBitNum(int n){
        int c =0 ;
        for (c =0; n!=0; ++c)
        {
            n &= (n -1) ; // 清除最低位的1
        }
        return c ;
    }





}
